/* ************************************************************************
> File Name:     main.cpp
> Author:        Sean
> Project:    LeetCode
> Created Time:  Mon Nov 15 21:11:22 2021
> Description:   
 ************************************************************************/
#include <vector> 
#include <iostream> 
#include <memory> 
#include <gtest/gtest.h> 

using namespace std; 

template <typename T> 
struct ListNode {
    T val; 
    shared_ptr<ListNode<T>> next; 
    ListNode() : val(0), next(nullptr) {

    }
    ListNode(int x) : val(x), next(nullptr) {

    }
    ListNode(int x, shared_ptr<ListNode<T>> next) : val(x), next(next) {

    }
};

template <typename T>
class Solution {
public:
    shared_ptr<ListNode<T>> mergeTwoLists(shared_ptr<ListNode<T>> l1, shared_ptr<ListNode<T>> l2) {
        // base case
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;

        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

TEST(Test21, SimpleTest) {
    auto l1 = make_shared<ListNode<int>>(1);
    auto l11 = make_shared<ListNode<int>>(2);
    auto l12 = make_shared<ListNode<int>>(4);
    l1->next = l11; 
    l11->next = l12; 

    auto l2 = make_shared<ListNode<int>>(1);
    auto l21 = make_shared<ListNode<int>>(3);
    auto l22 = make_shared<ListNode<int>>(4);
    l2->next = l21; 
    l21->next = l22; 

    Solution<int> s; 
    auto result = s.mergeTwoLists(l1, l2); 
    while (result != nullptr) {
        cout << result->val << " ";
        result = result->next;
    }
}

int main() {
    testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}
